Focusing on the issue that the 3-point and 4-point hill climbing algorithms have high calculation and low efficiency in enhancing the nonlinearity of a Substitution box (S-box), an algorithm named Combination of Hill Climbing (CHC), which could apply multiple swap elements at a time, was proposed. The algorithm defined the behavior of swapping 2 output data of an S-box as a swap element, and used weighting prioritizing function to select swap elements that have larger contribution to the enhancement of nonlinearity, then simultaneously applied multiple selected swap elements to enhance the nonlinearity of an S-box. In the experiments, a maximum of 12 output data were swapped at a time by using the CHC algorithm, and most of the random 8-input and 8-output S-boxes' nonlinearity surpassed 102, with a maximum of 106. The experimental results show that the proposed CHC algorithm not only reduces the amount of calculation, but also enhances the nonlinearity of random S-boxes more significantly in comparison with the 3-point and 4-point hill climbing algorithms.